๋ฌธ์
๐ Logic
private static void dfs(int cnt) {
if (cnt == n + 1) {
// ์ ์ ๊ณ์ฐ
int ryanScore = 0;
int apeachScore = 0;
for (int i = 0; i <= 10; i++) {
if (info[i] == 0 && ryan[i] == 0) continue;
if (info[i] < ryan[i]) ryanScore += 10 - i;
else apeachScore += 10 - i;
}
if (ryanScore > apeachScore && ryanScore - apeachScore >= max) {
max = ryanScore - apeachScore;
answer = ryan.clone();
}
return;
}
// ryan์ด ์ ํ์ด์ด info๋ณด๋ค ํฌ๋ฉด ์งํํ ํ์ ์์
for (int i = 0; i <= 10 && ryan[i] <= info[i]; i++) {
ryan[i]++;
dfs(cnt + 1);
ryan[i]--;
}
}
- DFS๋ก ๋ผ์ด์ธ์ด ์ดํผ์น๋ณด๋ค ํ์ด์ ๋ง์ด ์์ง ์์ ๊ฒฝ์ฐ์ ๋ํด ํ์ด์ ์๋ค.
-
1๋ถํฐ n+1๊น์ง ์งํํ๋ฉด์, ๋ผ์ด์ธ๊ณผ ์ดํผ์น์ ์ ์๋ฅผ ๊ณ์ฐํ๊ณ , ์ ์ ์ฐจ๊ฐ ํฐ ๊ฒฝ์ฐ๋ฅผ
max์ ๊ฐฑ์ ํ๋ฉด์ ๋ผ์ด์ธ์ ๊ณผ๋ ์ ์๋ฅผ ๊ฐฑ์ ํ๋ค.- ์ด๋
max๋ ๊ฐ์ ๊ฒฝ์ฐ์ฌ๋ ๊ฐฑ์ ํ๋๋ก ํ์ฌ, ์ ์ ์ฐจ๊ฐ ๊ฐ์ ๊ฒฝ์ฐ ๊ฐ์ฅ ๋ฎ์ ์ ์๋ฅผ ๋ง์ด ์ ๊ฒฝ์ฐ๋ก ๊ณผ๋ ์ ์๋ฅผ ๊ฐฑ์ ํ ์ ์๋๋ก ํ๋ค.
- ์ด๋
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
class Solution {
static int n;
static int[] info;
static int[] ryan;
static int[] answer = new int[]{ -1 };
static int max = 0;
public int[] solution(int n, int[] info) {
this.n = n;
this.info = info;
this.ryan = new int[11];
dfs(1);
return answer;
}
private static void dfs(int cnt) {
if (cnt == n + 1) {
// ์ ์ ๊ณ์ฐ
int ryanScore = 0;
int apeachScore = 0;
for (int i = 0; i <= 10; i++) {
if (info[i] == 0 && ryan[i] == 0) continue;
if (info[i] < ryan[i]) ryanScore += 10 - i;
else apeachScore += 10 - i;
}
if (ryanScore > apeachScore && ryanScore - apeachScore >= max) {
max = ryanScore - apeachScore;
answer = ryan.clone();
}
return;
}
// ryan์ด ์ ํ์ด์ด info๋ณด๋ค ํฌ๋ฉด ์งํํ ํ์ ์์
for (int i = 0; i <= 10 && ryan[i] <= info[i]; i++) {
ryan[i]++;
dfs(cnt + 1);
ryan[i]--;
}
}
}
โ๏ธ Review
- ์ฌ๊ท์ ์ธ ๋ฐฉ์์ผ๋ก ๋์ ์ ์๋ถํฐ ํ์ด์ ์ด๋ณด๋ฉด์ ์งํํด์ผ ํ๋ ๋ฌธ์ ์์ ์ฝ๊ฒ ์ ์ ์์๋ค.
- ์์ํ ๊ตฌํ์์ ๋งํ ํ์ด๋ฅผ ์ฐธ๊ณ ํ๋ค.